1226. Foreign Exchange

Your non-profit organization (iCORE – international Confederation of Revolver Enthusiasts) coordinates a very successful foreign student exchange program. Over the last few years, demand has sky-rocketed and now you need assistance with your task.

The program your organization runs works as follows: All candidates are asked for their original location and the location they would like to go to. The program works out only if every student has a suitable exchange partner. In other words, if a student wants to go from A to B, there must be another student who wants to go from B to A. This was an easy task when there were only about 10 candidates, however now there are up to 100001 candidates!

Input. The first line contains the number of tests t. The first line of each test contains the number of candidates n (1 ≤ n ≤ 100001). Next n lines represent the exchange information for each candidate. Each of these lines contains two integers, separated by a single space, representing the candidate's original location and the candidate's target location respectively. Locations will be represented by nonnegative integer numbers, not greater than 10⁹. You may assume that no candidate will have his or her original location being the same as his or her target location as this would fall into the domestic exchange program.

Output. For each test case in a separate line print “YES” if there is a way for the exchange program to work out, or “NO” otherwise.

Sample input

2

10

1 2

2 1

3 4

4 3

100 200

200 100

57 2

2 57

1 2

2 1

10

1 2

3 4

5 6

7 8

9 10

11 12

13 14

15 16

17 18

19 20

Sample output

YES

NO

SOLUTION

data structures - multiset

Algorithm analysis

It is enough for each pair (А, В) to put in correspondence the pair (В, А). Input pairs can be repeated. To store the data we shall use the multiset. For each input pair (А, В) we’ll find in the multiset the pair (B, A). If such pair exists, delete it. Otherwise insert in multiset the pair (А, В). If after the end of data processing the multiset will be empty, it means that for each pair (А, В) the pair (В, А) was found, so the exchange program will work.

Example

In the first test for each pair (A, B) can be found the correspondent pair (B, A). In the second test no one student desire can be fulfilled.

Algorithm realization

Declare the multiset of pairs s. In the process of running program we keep there only those pairs (А, В), for which there is no corresponding pair (В, А).

multiset<pair<int,int> > s;

multiset<pair<int,int> >::iterator iter;

Read the number of tests t.

scanf("%d",&t);

After reading the number of students n, clear the multiset s. For each input pair (А, В) check, does the multiset contain the pair (В, А). If the answer is yes, then delete (В, А), otherwise insert (А, В).

while(t--)

{

scanf("%d",&n); s.clear();

for(i = 0; i < n; i++)

{

scanf("%d %d",&a,&b);

if ((iter = s.find(make_pair(b,a))) == s.end()) s.insert(make_pair(a,b));

else s.erase(iter);

}

If at the end of data processing for one test case the multiset s is empty, then each pair (А, В) has its corresponding pair (В, А), so the exchange program will work.

if (s.empty()) printf("YES\n");

else printf("NO\n");

}